//058. 螺旋质数
//        从 1 开始按以下方式逆时针旋转，可以形成一个边长为 7 的正方形螺旋：
//        有趣的是奇数的平方数都处于右下对角线上。更有趣的是，对角线上的 13 个数字中有 8 个
//        质数，其百分比是 8/13 ≈ 62%。
//        如果在上面的螺旋正方形上再加一层，可以得到一个边长为 9 的螺旋正方形。如果这个过
//        程继续，到螺旋正方形的边长为多少时，对角线上的质数百分比第一次降到 10% 以下？
//        答案：26241

//n圈，则边长为2*n-1
//右下↘对角线的数为(2*n-1)^2                =4(n^2)-4n+1
//左下↙对角线的数为(2*n-1)^2 - (2*n-2)        =4(n^2)-6n+3
//左上↖对角线的数为(2*n-1)^2 - 2*(2*n-2)    =4(n^2)-8n+5
//右上↗对角线的数为(2*n-1)^2 - 3*(2*n-2)    =4(n^2)-10n+7
public class Week058 {
    //余6法
    //当x%6=±1时，x可能是质数，否则一定不是质数
    public static boolean isPrime(int n) {
        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        for (int i = 5, sq = (int) Math.sqrt(n); i <= sq; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    static void run() {
        long all = 5, prime = 3;
        int n = 2;
        while ((double) prime / all - 0.1 >= 1e-9) {
            ++n;
            all += 4;
            if (isPrime(4 * n * n - 4 * n + 1)) ++prime;
            if (isPrime(4 * n * n - 6 * n + 3)) ++prime;
            if (isPrime(4 * n * n - 8 * n + 5)) ++prime;
            if (isPrime(4 * n * n - 10 * n + 7)) ++prime;
        }
//        System.out.println("all=" + all + ", prime=" + prime);
        System.out.println(2 * n - 1);
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        run();
        System.out.println("\n程序运行时间：" + (System.currentTimeMillis() - startTime) + "ms.");
    }
}
